package org.leetcode.easy.leetcode160;

import org.leetcode.easy.ListNode;

import java.util.HashSet;
import java.util.Set;

public class Solution
{

    class ListNode{
        int val;
        ListNode next;
        public ListNode (int val){
            this.val=val;
            this.next=null;
        }

        public ListNode(int val,ListNode nextNode){
            this.val=val;
            this.next=nextNode;
        }
    }


    public ListNode getIntersectionNode3(ListNode headA, ListNode headB){

        Set<ListNode> set = new HashSet<>();

        while (headA!=null){
            set.add(headA);
            headA=headA.next;
        }

        while (headB!=null){
            if (set.contains(headB)){
                return headB;
            }else {
                headB=headB.next;
            }
        }

        return null;
    }

    /**
     * 未解决
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {


        if (headA==null || headB==null)
        {
            return null;
        }

        ListNode dummyHeadA = new ListNode(0,headA);
        ListNode dummyHeadB = new ListNode(-1,headB);

        dummyHeadA=dummyHeadA.next;

        dummyHeadB=dummyHeadB.next;

        while ( dummyHeadA!=null && !dummyHeadA.equals(dummyHeadB)  )
        {
            dummyHeadA=dummyHeadA.next;
        }

        if (dummyHeadA==null)
        {
            dummyHeadA=headA;

            while (dummyHeadB!=null &&!dummyHeadB.equals(dummyHeadA))
            {
                dummyHeadB=dummyHeadB.next;
            }

            if (dummyHeadB==null)
            {
                return  null;
            }else {
                return dummyHeadB;
            }

        }else {
            return dummyHeadA;
        }


    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB)
    {

        ListNode curA = headA;
        ListNode curB = headB;

        int headALength = getListLength(headA);
        int headBLength = getListLength(headB);


        if (headBLength>headALength)
        {
            ListNode temp =curB;
            curB=curA;
            curA=temp;
        }

        int Gap = Math.abs(headALength-headBLength);

        while (Gap!=0)
        {
            curA=curA.next;
            Gap--;
        }

        while (curA!=null)
        {
            if (curA==curB)
            {
                return curA;
            }

            curA=curA.next;
            curB=curB.next;
        }



        return null;
    }


    /**
     * 计算链表长度
     * @param listNode
     * @return
     */
    private int getListLength(ListNode listNode)
    {
        int index =0;

        while (listNode!=null)
        {
            index++;
            listNode=listNode.next;
        }

        return index;
    }


    public static void main(String[] args) {
//        ListNode sameNode = new ListNode(3, null);
//        ListNode listA = new ListNode(4, new ListNode(1, null));
//        ListNode listB = new ListNode(5, new ListNode(1, null));
////
//        listA.next.next=sameNode;
//        listB.next.next=sameNode;
////
////        boolean equals = listA.next.next.equals(listB.next.next);
////
////        System.out.println(equals);
//
//        Solution solution = new Solution();
//        ListNode intersectionNode = solution.getIntersectionNode(listA, listB);

    }
}
